package Heap;

import java.util.Arrays;

public class TestHeap {
    public int[] elem;//成员是数组
    public int usedsize;

    public TestHeap(){
        this.elem = new int[10];
    }

    //初始化elem数组
    public void initElem(int[] array){
        for(int i = 0;i<array.length;i++){
            elem[i] = array[i];
            usedsize++;
        }
    }


    //创建大根堆
    public void creatBigHeap(){
        for (int parent = (usedsize-1-1)/2;parent>=0;parent--){
            siftDown(parent,usedsize);
        }
    }


    //创建大根堆
    public void siftDown(int parent,int end){//结束位置
        int child = 2*parent+1;
        while (child<end){
            if(child+1<usedsize||elem[child]<elem[child+1]){
                child++;
            }
            //child是左右孩子最大值的下标
            if(elem[child]>elem[parent]){
                swap(child,parent);
                parent = child;
                child = 2*parent+1;
            }else{
                break;
            }
        }

    }

    public void swap(int i,int j){
        int rmp = elem[i];
        elem[i] = elem[j];
        elem[j] = rmp;
    }

    public int poll(){
        int tmp = elem[0];
        swap(0,usedsize-1);
        usedsize--;
        siftDown(0,usedsize);
        return tmp;
    }

    //插入
    public void offer(int val){
    //判断数组是否满
        if(isFull()){
            //扩容
            this.elem = Arrays.copyOf(elem,2*elem.length);
        }
        //插入元素到最后
        elem[usedsize] = val;
        usedsize++;

        //向上调整
        siftUp(usedsize-1);
    }

    public void siftUp(int child){
        int parent = (child-1)/2;
        while (child>0){
            if(elem[parent]<elem[child]){
                swap(parent,child);
                child = parent;
                parent = (child-1)/2;
            }else{
                break;
            }
        }
    }

    public boolean isFull(){
        return usedsize==elem.length;
    }




    public void heapSort(){
        //堆排序,建立大根堆
        int end = usedsize-1;
        while(end>0){
            swap(0,end);
            siftDown(0,end-1);
            end--;
        }
    }

 }
